/* Given a sequence of integers a[0...N-1], the task is to find two
 * non-overlapping ranges a[i...j] and a[k...l] such that the sum of these
 * elements are maximized.
 *
 * To do this, we try each of the cut-off positions (after a[0]...a[N-2]),
 * and sum up the largest sum on each side. This is done in two phases: in
 * phase one, we compute a running maximum sum from a[0] to a[i] for each
 * i = 0..N-2. This takes linear time. In phase two, we compute the running
 * max sum from a[N-1] down to a[j] for each j = N-1 down to a[1]. We then
 * compute the sum at each cut-off point to find the maximum.
 */

#include <stdio.h>

static int a[50000];
static int running_max[50000];
static int N;

static int solve()
{
    /* Compute a running maximum subsequence sum from a[0] to a[i] for each
     * i = 0 to N-2. */
    int i, result = -20000;
    int sum = 0;            /* running sum from a[0] to a[i] */
    int min_sum = 0;        /* running minimum of the running sum */
    int max_sum = -10000;   /* running maximum subsequence sum */
    for (i = 0; i < N-1; i++)
    {
        sum += a[i];
        if (sum - min_sum > max_sum)
            max_sum = sum - min_sum;
        if (sum < min_sum)
            min_sum = sum;
        running_max[i] = max_sum;
    }

    /* Compute backword from a[N-1] down to a[i] for i = N-1 down to 1. */
    sum = min_sum = 0;
    max_sum = -10000;
    for (i = N-1; i > 0; i--)
    {
        sum += a[i];
        if (sum - min_sum > max_sum)
            max_sum = sum - min_sum;
        if (sum < min_sum)
            min_sum = sum;
        if (max_sum + running_max[i-1] > result)
            result = max_sum + running_max[i-1];
    }
    return result;
}

int main()
{
    int T, t;
    scanf("%d", &T);
    for (t = 0; t < T; t++)
    {
        int i;
        scanf("%d", &N);
        for (i = 0; i < N; i++)
            scanf("%d", &a[i]);
        printf("%d\n", solve());
    }
    return 0;
}
